import java.util.LinkedList;


public class No021 {
    /**
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的  **相对位置不变**。
     */
    public void reOrderArray(int[] array) {
        if (array.length == 0) return;
        LinkedList<Integer> queueOdd = new LinkedList<>();
        LinkedList<Integer> queueEven = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1) {
                queueOdd.addLast(array[i]);
            } else {
                queueEven.addLast(array[i]);
            }
        }
        int i = 0;
        while (!queueOdd.isEmpty()) {
            array[i++] = queueOdd.removeFirst();
        }
        while (!queueEven.isEmpty()) {
            array[i++] = queueEven.removeFirst();
        }
    }
}
